МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ „ЛЬВІВСЬКА ПОЛІТЕХНІКА” ІКТА Кафедра захисту інформації З В І Т До лабораторної роботи №5 з курсу: „ Комп’ютерні методи дослідження інформаційних процесів та систем ” на тему: «Метод Ньютона для розв’язування систем нелінійних рівнянь» Варіант 19 Львів- 2010 Мета роботи: Ознайомлення з найпоширенішим ітераційним методом розв’язування систем нелінійних рівнянь – методом Ньютона. Вступ Систему нелінійних рівнянь у загальному випадку можна зобразити у вигляді
Тобто як
функцій
від
невідомих
, причому функції
не обов’язково лінійно залежить від змінних
. Позначимо вектор змінних через
, а вектор функції через
. Тоді систему (1) можна записати у формі.
Завдання полягає в тому, щоб знайти розв’язок цієї системи. Слід сказати, що на даний час не існує математичної теорії, яка дозволяла б у загальному вигляді розв’язати питання про існування та число розв’язків системи (2). Їх може не бути зовсім, може бути один, декілька або нескінчена множина [3]. Крім того, важливою особливістю системи нелінійних рівнянь є те, що для їх розв’язків не можна використати прямі методи, зокрема, метод послідовного виключення невідомих. Усі розробленні методи є ітераційними, а найефективнішим і широко вживаним є метод Ньютона. 1. Стандартний метод Ньютона Метод Ньютона базується на лінеаризації задачі і заміні розв'язування нелінійної системи (2) на послідовність розв'язувань лінійних систем (найчастіше прямими методами). Будемо вважати, що система рівнянь (2) має розв'язок; позначимо його через вектор
і розкладемо кожну функцію в ряд Тейлора в околі розв'язку
де
- члени другого і вищих порядків. Вважаючи, що
дуже близьке до
, знехтуємо членами вищих порядків і запишемо систему рівнянь в лінеаризованій формі:
(3) або в іншому вигляді
(4) де
– матриця Якобі (якобіан) системи (1) Враховуючи, що
є розв'язком системи, згідно з (2) можемо записати:
Звідси випливає, що і праву частину (4) також можна прирівняти до нуля:
(5) Розв'язком системи (5) є нове значення вектора X, яке не точно дорівнює значенню вектора
(оскільки знехтували членами другого і вищих порядків). Використовуючи верхні індекси для позначення послідовності ітерацій, можна записати
(6) Звідси
(7) де
- обернена матриця Якобі;
. У достатньо широкому околі розв'язку
ітераційний процес (7) збігається, якщо
. Ітераційний процес закінчується при виконанні умови
(8) де Σ - задана гранична похибка уточнень коренів системи (1). Таким чином, алгоритм стандартного методу Ньютона можна розбити, на декілька кроків. Крок 1. Вибір вектора початкових уточнень
. Крок 2. Обчислення елементів матриці Якобі. Крок 3. Обчислення елементів оберненої матриці Якобі. Крок 4. Перемноження значень функції (див. формулу (7))
Крок 5. Одержаний на кроці 4 вектор віднімається від вектора
, у результаті чого одержується покращений вектор розв'язку
. Крок 6. Перевірка умови закінчення ітерацій (8). Якщо вона не виконується, то за вектор початкових уточнень приймається вектор
і проводиться наступна ітерація, починаючи з кроку 2. При використанні стандартного методу Ньютона слід мати на увазі наступне. 1. Стандартний метод Ньютона надзвичайно ефективний. 2. Збіжність на початку ітераційного процесу, як правило, лінійна. 3. Починаючи з деякого кроку ( уточнити його попередньо неможливо), збіжність різко прискорюється і стає квадратичною. 4. Бувають випадки, коли метод розбігається або спостерігається зациклювання ітерацій. Тому необхідно обмежувати максимальну кількість ітерацій деяким попередньо заданим числом. Основний недолік методу полягає в повторних обчисленнях на кожному кроці вектора
, матриці Якобі
, оберненої матриці Якобі
. 3. Модифікований метод Ньютона При використанні стандартного методу Ньютона на кожній ітерації доводиться обчислювати новий якобіан
, хоч зрозуміло, що при закінченні ітерацій він повинен прийняти стабільне значення
, де
–розв'язок. У модифікованому або спр...